package com.hspedu.newData.dmsxl.堆;

import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-04-29 
 * @Version: 1.0
 */

public class LC215数组中的第k个最大元素 {

    // 小根堆的解法 时间复杂度是O（nlogk）
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
                new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o1 - o2;
                    }
                }
        );

        for (int i = 0; i < nums.length; i++) {
            minHeap.offer(nums[i]);
            if (minHeap.size() > k){
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }

    // todo 快排方法

    @Test
    public void test() {
        // 测试代码
        int kthLargest = findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2);
        int kthLargest1 = findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 4);
        System.out.println("-----");
    }
}
